#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<int>& prices){
        if(prices.empty()){
            return 0;
        }

        int len = prices.size();
        int k = min(2, len/2);
        vector<int> buy(k+1, INT32_MIN/2);
        vector<int> sell(k+1, INT32_MIN/2);

        buy[0] = -prices[0];
        sell[0] = 0;

        for(int i = 1; i != len; i++){
            buy[0] = max(buy[0], sell[0] - prices[i]);
            for(int j = 1; j != k+1; j++){
                buy[j] = max(buy[j], sell[j] - prices[i]);
                sell[j] = max(sell[j], buy[j-1] + prices[i]);
            }
        }

        return *max_element(sell.begin(), sell.end());

    }

};

void test1(){
    Solution s;
    vector<int> prices = {3,3,5,0,0,3,1,4};

    int ret = s.ans1(prices);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> prices = {1,2,3,4,5};

    int ret = s.ans1(prices);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> prices = {7,6,4,3,1};

    int ret = s.ans1(prices);
    cout << ret << endl;
}


int main(void){
    test1();
    test2();
    test3();

    return 0;
}